package www.study.com;

//搜索旋转排序数组 https://leetcode.cn/problems/search-in-rotated-sorted-array/
public class code33 {
    public static void main(String[] args) {

    }

    class Solution {
        //答案有问题
        public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            while(l <= r){
                int mid = l + ((r - l) >> 1);
                System.out.println("mid: " + mid);
                if(nums[mid] == target){
                    return mid;
                }
                //注意：如果[0...mid-1]有序，那么[mid+1...nums.length-1]无序，至少一个区间有序
                if(nums[0] <= nums[mid - 1]){ //[0...mid-1]有序
                    if(nums[0] <= target && target < nums[mid]){ //target在右区间
                        r = mid - 1;
                    }else{
                        l = mid + 1;
                    }
                }else{ //[mid+1...nums.length-1]有序
                    if(mid + 1 < nums.length && nums[mid + 1] <= target && target <= nums[nums.length - 1]){ //target在右区间
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    }
}
